package JanChallenges;

import BasicDataStructures.TreeNode;
import Utils.TreeUtils;

import java.io.FilterOutputStream;
import java.util.*;

//https://leetcode.com/problems/amount-of-time-for-binary-tree-to-be-infected/description/?envType=daily-question&envId=2024-01-10
public class Day10_P2385 {
    public static void main(String[] args) {
        String data = "153#476##92";
        TreeNode root = TreeUtils.generateTree(data);
        assert root != null;
        System.out.println(amountOfTime(root, 3));
    }

    public static int amountOfTime(TreeNode root, int start) {
        HashMap<Integer, Node> nMap = new HashMap<>();
        nMap.put(root.val, new Node(root.val));
        fillMap(root, nMap);
        return getTime(nMap, start);
    }

    public static void fillMap(TreeNode cur, HashMap<Integer, Node> nMap) {
        if(cur != null) {
            int curVal = cur.val;
            Node curNode = nMap.get(curVal);
            if(cur.left != null) {
                Node leftNode = new Node(cur.left.val);
                curNode.nexts.add(leftNode);
                leftNode.nexts.add(curNode);
                nMap.put(leftNode.val, leftNode);
                fillMap(cur.left, nMap);
            }
            if(cur.right != null) {
                Node rightNode = new Node(cur.right.val);
                curNode.nexts.add(rightNode);
                rightNode.nexts.add(curNode);
                nMap.put(rightNode.val, rightNode);
                fillMap(cur.right, nMap);
            }
        }
    }

    public static int getTime(HashMap<Integer, Node> nMap, int s) {
        Node start = nMap.get(s);
        LinkedList<Node> ll = new LinkedList<>();
        HashSet<Integer> visited = new HashSet<>();

        ll.offer(start);
        visited.add(start.val);
        int day = 0;
        while(!ll.isEmpty()) {
            int size = ll.size();
            for(int i = 0; i < size; i++) {
                Node cur = ll.poll();
                for(Node next:cur.nexts) {
                    if(!visited.contains(next.val)) {
                        ll.offer(next);
                        visited.add(next.val);
                    }
                }
            }
            day++;
        }
        return day - 1;
    }

    public static class Node {
        List<Node> nexts;
        int val;

        public Node(int val) {
            nexts = new ArrayList<>();
            this.val = val;
        }
    }
}
